{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Smallest Divisor Given a Threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestDivisor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使结果不超过阈值的最小除数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> 和一个正整数&nbsp;<code>threshold</code> &nbsp;，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。</p>\n",
    "\n",
    "<p>请你找出能够使上述结果小于等于阈值&nbsp;<code>threshold</code>&nbsp;的除数中 <strong>最小</strong> 的那个。</p>\n",
    "\n",
    "<p>每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。</p>\n",
    "\n",
    "<p>题目保证一定有解。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,5,9], threshold = 6\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。\n",
    "如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,5,7,11], threshold = 11\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [19], threshold = 5\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10^4</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10^6</code></li>\n",
    "\t<li><code>nums.length &lt;=&nbsp;threshold &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-smallest-divisor-given-a-threshold](https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-smallest-divisor-given-a-threshold](https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5,9]\\n6', '[44,22,33,11,1]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def check(x):\n",
    "            if x == 0:return False\n",
    "            return sum(ceil(i/x) for i in nums)<=threshold\n",
    "        return bisect_left(range(max(nums)),x=True,key = check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "# 1283. 使结果不超过阈值的最小除数\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left,right=1,max(nums)\n",
    "        ans=right\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "            divSum=sum((x+mid-1)//mid for x in nums)\n",
    "            if divSum<=threshold:\n",
    "                ans=mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def func(nums,n):\n",
    "            return  sum(ceil(i/n) for i in nums)\n",
    "\n",
    "\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        \n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            total = func(nums,mid)\n",
    "            \n",
    "            if total > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from ctypes import *\n",
    "import mmap\n",
    "\n",
    "buf=mmap.mmap(-1,mmap.PAGESIZE,prot=mmap.PROT_READ|mmap.PROT_WRITE|mmap.PROT_EXEC)\n",
    "\n",
    "ftype=CFUNCTYPE(c_int,POINTER(c_int),c_int)\n",
    "fpointer=c_void_p.from_buffer(buf)\n",
    "\n",
    "f=ftype(addressof(fpointer))\n",
    "\n",
    "buf.write(\n",
    "    b'\\x89\\xd3'  # mov ebx,edx\n",
    "    b'\\xb9\\x00\\x00\\x00\\x00'  # mov ecx,0\n",
    "    b'\\x48\\x8d\\x34\\xb7'  # lea rsi,[rsi*4+rdi]\n",
    "    # begin:\n",
    "    b'\\x8b\\x07'  # mov eax,DWORD PTR [rdi]\n",
    "    b'\\xba\\x00\\x00\\x00\\x00'  # mov edx,0\n",
    "    b'\\xf7\\xfb'  # idiv ebx\n",
    "    b'\\x01\\xc1'  # add ecx,eax\n",
    "    b'\\x48\\x8d\\x7f\\x04'  # lea rdi,0x4[rdi]\n",
    "    b'\\x48\\x39\\xf7'  # cmp rdi,rsi\n",
    "    b'\\x74\\x02'  # jz end\n",
    "    b'\\xeb\\xea'  # jmp begin\n",
    "    # end:\n",
    "    b'\\x89\\xc8'  # mov eax,ecx\n",
    "    b'\\xc3'  # ret\n",
    ")\n",
    "\n",
    "#del fpointer\n",
    "#buf.close()\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums=[x-1 for x in nums]\n",
    "        a=(c_int*n)()\n",
    "        for i in range(n): a[i]=nums[i]\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = f(a,n,mid)\n",
    "            total+=n\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def div_sum(x):\n",
    "            return sum((n + x - 1) // x for n in nums)\n",
    "\n",
    "        # 二分查找？\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = div_sum(mid)\n",
    "            if total > threshold:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def cal(x):\n",
    "            return sum(ceil(i/x) for i in nums)\n",
    "        \n",
    "        l, r = 1, max(nums)\n",
    "        while l <= r:\n",
    "            mid = (l + r)//2\n",
    "            if cal(mid) > threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums)\n",
    "        while left + 1 <right:\n",
    "            mid = (left + right)//2\n",
    "            if sum((r + mid -1)//mid for r in nums)<=threshold:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        cnt = sum(nums)\n",
    "        if cnt<=threshold:\n",
    "            return 1\n",
    "        l = cnt//threshold\n",
    "        r = max(nums)+1\n",
    "        ans = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            cnt = sum((x-1)//mid+1 for x in nums)\n",
    "            if cnt<=threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        # tmp <= threshold\n",
    "        if sum(nums) <= threshold:\n",
    "            return 1\n",
    "        \n",
    "        l, r = 1, max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            tmp = sum(math.ceil(num / mid) for num in nums)\n",
    "            if tmp > threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        import math\n",
    "        l,r = 1,max(nums)\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if sum(math.ceil(p/mid) for p in nums) <= threshold:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((num - 1) // mid + 1 for num in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "\n",
    "        def valid(num):\n",
    "            total = sum((v + num - 1) // num for v in nums)\n",
    "            return total <= threshold\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if valid(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum((i - 1) // mid + 1 for i in nums) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 ~ threshold\n",
    "    def getSum(self, nums: List[int], x: int) -> int:\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += math.ceil(num / x)\n",
    "        return sum\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.getSum(nums, mid) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums)\n",
    "        while left + 1 <right:\n",
    "            mid = (left + right)//2\n",
    "            if sum((r + mid -1)//mid for r in nums)<=threshold:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def div_sum(x):\n",
    "            return sum((n + x - 1) // x for n in nums)\n",
    "\n",
    "        # 二分查找？\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = div_sum(mid)\n",
    "            if total > threshold:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def div_sum(k: int) -> int:\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                cnt += math.ceil(num / k)\n",
    "            return cnt\n",
    "\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if div_sum(mid) > threshold:\n",
    "                left =mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def check(div: int) -> bool:\n",
    "            return sum((num + div - 1) // div for num in nums) <= threshold\n",
    "        n = len(nums)\n",
    "        l, r = 1, max(nums)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        # print(l, r)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        # 二分查找\n",
    "        l = 1\n",
    "        r = max(nums)\n",
    "\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = sum((n + mid - 1) // mid for n in nums)\n",
    "            if total > threshold:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        ans = 0\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            result = sum(math.ceil(v/mid) for v in nums)\n",
    "            if result > threshold:\n",
    "                left = mid + 1\n",
    "            # else result <= threshold\n",
    "            else: \n",
    "                right = mid - 1\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def divide(a, b):\n",
    "    return math.ceil(a / b)\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    最小化最大值类型：\n",
    "        给你一个整数数组 nums 和一个正整数 threshold  ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。\n",
    "        请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。\n",
    "        每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。 题目保证一定有解。\n",
    "    \"\"\"\n",
    "\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        \"\"\"\n",
    "        最小化最大值问题，使用二分法求解：\n",
    "        1. 先将数组从小到达排序\n",
    "        2. 循环不变量:\n",
    "            1. left 的左边都是满足题目要求小于等于阈值的正整数, 但是除数之和从大到小进行排序\n",
    "            2. right 的右边都是不满足题目条件的正整数\n",
    "        :param nums:\n",
    "        :param threshold:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        left, right = 1, 10 ** 6\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum(divide(num, mid) for num in nums) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        # 二分查找\n",
    "        l = max(sum(nums) // threshold, 1)\n",
    "        r = max(nums)\n",
    "\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = sum((n + mid - 1) // mid for n in nums)\n",
    "            if total > threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if sum(map(lambda x: (x - 1) // mid + 1, nums)) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l,r,res=1,max(nums)+1,-1\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total=sum((x-1)//mid+1 for x in nums)\n",
    "            if total<=threshold:\n",
    "                res=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        #解题思路：\n",
    "        #二分查找\n",
    "        #注意：当除数 d >= M 时，数组 nums 中的每个数除以 d 的结果均为 1\n",
    "\n",
    "        def fun1(x):\n",
    "            res = sum([math.ceil(i / x) for i in nums])\n",
    "            return res\n",
    "        \n",
    "        l,r = 1,max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            cur = fun1(mid)\n",
    "            if cur <= threshold:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def summation(nums,divisor,threshold):\n",
    "            ans = 0\n",
    "            for num in nums:\n",
    "                if num%divisor:\n",
    "                    ans+=1\n",
    "                ans+= num//divisor\n",
    "            return ans<=threshold\n",
    "        n = len(nums)\n",
    "        right = max(nums)\n",
    "        if threshold == n:\n",
    "            return right\n",
    "        left = 1\n",
    "        \n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if summation(nums,mid,threshold):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def ck(x):\n",
    "            tot = 0\n",
    "            for c in nums:\n",
    "                tot += (c + x - 1) // x\n",
    "            return tot <= threshold \n",
    "        l, r = 1, int(1e6 + 10)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if ck(mid): r = mid \n",
    "            else: l = mid + 1 \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lower_bound(nums: List[int], threshold: int) -> int:\n",
    "    \"\"\"\n",
    "        最小化最大值问题，使用二分法求解, 左闭右开区间写法：\n",
    "        1. 循环不变量:\n",
    "            1. left 的左边都是满足题目要求小于等于阈值的正整数, 但是除数之和从大到小进行排序\n",
    "            2. right 的右边都是不满足题目条件的正整数\n",
    "        最终的结果是 left = right + 2 所以返回 left 或者 right + 2 都行\n",
    "        :param nums:\n",
    "        :param threshold:\n",
    "        :return:\n",
    "    \"\"\"\n",
    "    left, right = 1, 10 ** 6 + 1\n",
    "    while left <= right + 1:\n",
    "        mid = (left + right + 1) // 2\n",
    "        if sum(math.ceil(num / mid) for num in nums) > threshold:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 2\n",
    "    return left\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    最小化最大值类型：\n",
    "        给你一个整数数组 nums 和一个正整数 threshold  ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。\n",
    "        请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。\n",
    "        每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。 题目保证一定有解。\n",
    "    \"\"\"\n",
    "\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        return lower_bound(nums, threshold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            mid=(left+right)//2\n",
    "            if sum(math.ceil(num / mid) for num in nums) > threshold:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right =mid\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left,right = 1,max(nums)\n",
    "        nums.sort()\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum([ceil(num / mid) for num in nums]) <= threshold:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        l, r, ans = 1 , max(nums) + 1, -1\n",
    "\n",
    "        while l <= r: \n",
    "\n",
    "            mid = (l + r) //2 \n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            \n",
    "            if total <= threshold: \n",
    "                ans = mid\n",
    "                r = mid - 1 \n",
    "            else: \n",
    "                l = mid + 1 \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\r\n",
    "\r\n",
    "        def sum_array(num):\r\n",
    "            # * 巧妙向上取整\r\n",
    "            return sum(((i-1)//num + 1) for i in nums)\r\n",
    "\r\n",
    "        left = 1\r\n",
    "        right = max(nums)\r\n",
    "\r\n",
    "        while left <= right:  # 闭区间二分, 终止条件为空区间\r\n",
    "            mid = (left+right)//2\r\n",
    "\r\n",
    "            if sum_array(mid) > threshold:  # 结果大于阈值, 说明mid取小了\r\n",
    "                left = mid + 1\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "\r\n",
    "        # - 终止条件: left = right = mid = thre\r\n",
    "        # - 或 left = right = mid > thre ?\r\n",
    "        # ! 解释下为啥是>thre, 最后一轮, 一定是left=right=mid毋庸置疑,\r\n",
    "        # ! 因为这是最后一个不是空区间的区间, 区间长度为1\r\n",
    "        # - 其次, left只有符合条件才会移动(if条件), 因此left左边不可能有小于阈值的数\r\n",
    "        # - 所以最后一轮循环left一定染色, 并染成蓝色(这与if 条件是 > 而不是 >=有关)\r\n",
    "        # - 那这就说明right移动到了不是自己区间的位置, 发生的越界\r\n",
    "        # - 因此最后left = mid + 1执行完成后一定来到了right的区间\r\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 1, nums[-1]\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            sum = self.divide(nums, mid)\n",
    "            if sum <= threshold:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r + 1\n",
    "\n",
    "    def divide(self, nums, shu) -> int:\n",
    "        return sum(ceil(num / shu) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def ck(x):\n",
    "            tot = 0\n",
    "            for c in nums:\n",
    "                tot += (c + x - 1) // x\n",
    "            return tot <= threshold \n",
    "        l, r = 1, max(nums) + 1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if ck(mid): r = mid \n",
    "            else: l = mid + 1 \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums) + 1\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            total = sum(math.ceil(num / mid) for num in nums)\n",
    "            if threshold < total:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 ~ threshold\n",
    "    def getSum(self, nums: List[int], x: int) -> int:\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += (num + x - 1) // x\n",
    "        return sum\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.getSum(nums, mid) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 超时 n^2\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "#         def roundUp(x, y):\n",
    "#             if x % y != 0:\n",
    "#                 return x // y + 1\n",
    "#             else:\n",
    "#                 return x // y \n",
    "\n",
    "#         maxOne = max(nums)\n",
    "#         for divisor in range(1, maxOne+1):\n",
    "#             total = 0\n",
    "#             for n in nums:\n",
    "#                 total += roundUp(n, divisor) #(n - 1 ) // divisor + 1    #math.ceil( n / divisor)\n",
    "#             print(total)\n",
    "#             if total <= threshold:\n",
    "#                 return divisor\n",
    "\n",
    "# O(N*logM) # n = len(nums), m = max(nums)\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        def roundUp(x, y):\n",
    "            if x % y != 0:\n",
    "                return x // y + 1\n",
    "            else:\n",
    "                return x // y \n",
    "\n",
    "        l, r, ans = 1, max(nums), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(roundUp(n, mid) for n in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/solutions/101358/shi-jie-guo-bu-chao-guo-yu-zhi-de-zui-xiao-chu-s-3/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left =1\n",
    "        right = max(nums)\n",
    "        if threshold== len(nums):\n",
    "            return right\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if sum([(num+mid-1)//mid for num in nums])<=threshold:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\r\n",
    "        lf, rt = 1, max(nums)\r\n",
    "        while lf < rt:\r\n",
    "            mid = (lf + rt) // 2\r\n",
    "            if sum((num + mid - 1) // mid for num in nums) > threshold:\r\n",
    "                lf = mid + 1\r\n",
    "            else:\r\n",
    "                rt = mid\r\n",
    "        return lf\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        r = max(nums)+1\n",
    "        l = 1\n",
    "        def check(x):\n",
    "            s = 0\n",
    "            for n in nums:\n",
    "                s += math.ceil(n/mid)\n",
    "            if s<=threshold:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            # sum_nums = sum( ceil(n/mid) for n in nums)\n",
    "            if check(mid): # 意味当前除数太小，不符合要求\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        limit = max(nums)\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                if(num % x == 0):\n",
    "                    res += num // x\n",
    "                else:\n",
    "                    res += num // x + 1\n",
    "            return res <= threshold\n",
    "        left, right = 1, limit\n",
    "        while(left <= right):\n",
    "            mid = (left + right) // 2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        while left < right:\n",
    "            divisor = (left + right) // 2\n",
    "            total = 0\n",
    "            for num in nums:\n",
    "                # total += (num // divisor)\n",
    "                # if num % divisor != 0:\n",
    "                #     total += 1\n",
    "                total += (num - 1) // divisor + 1\n",
    "            if total <= threshold:\n",
    "                right = divisor\n",
    "            else:\n",
    "                left = divisor + 1\n",
    "            \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "        l = len(nums)\n",
    "        while left < right:\n",
    "            \n",
    "            mid = (left + right) // 2\n",
    "            print(left, right, mid)\n",
    "            if sum(math.ceil(x / mid) for x in nums) > threshold:\n",
    "                left = mid + 1\n",
    "            elif sum(math.ceil(x / mid) for x in nums) <= threshold:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def check(div: int) -> bool:\n",
    "            return sum(ceil(num / div) for num in nums) <= threshold\n",
    "        n = len(nums)\n",
    "        l, r = 0, max(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def M1(self, nums: List[int], threshold: int) -> int:\r\n",
    "        \r\n",
    "        # def get_sum(mid):\r\n",
    "        #     return \r\n",
    "\r\n",
    "        # 搜索区间： [1, ]\r\n",
    "        left, right = 1, max(nums)\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            mid_v = sum([math.ceil(num / mid) for num in nums])\r\n",
    "            if mid_v > threshold:\r\n",
    "                # 和偏大，mid偏小了\r\n",
    "                left = mid + 1\r\n",
    "            # elif mid_v < threshold:\r\n",
    "                # 符合解\r\n",
    "                # 和偏小，mid偏大了\r\n",
    "                # right = mid - 1\r\n",
    "            else: # mid_V = threshold\r\n",
    "                # 符合解\r\n",
    "                right = mid - 1\r\n",
    "\r\n",
    "        return left\r\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\r\n",
    "        return self.M1(nums, threshold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def check(self, nums: List[int], threshold: int, divisor:int):\n",
    "        sum_of_nums = sum([math.ceil(i / divisor) for i in nums])\n",
    "        return sum_of_nums <= threshold\n",
    "\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        low = math.ceil(sum(nums) / threshold)\n",
    "        high = max(nums)\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if not self.check(nums, threshold, mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l, r, ans = 1, max(nums) + 1, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in nums)\n",
    "            if total <= threshold:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def isValid(self, nums, divisor, threshold):\n",
    "        res = 0.0\n",
    "        for num in nums:\n",
    "            res += math.ceil(float(num) / float(divisor))\n",
    "        return res <= threshold\n",
    "\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        small: int = 1\n",
    "        big: int = sum(nums)\n",
    "\n",
    "        while small + 1 < big:\n",
    "            mid = (small + big) // 2\n",
    "            if self.isValid(nums, mid, threshold):\n",
    "                big = mid\n",
    "            else:\n",
    "                small = mid\n",
    "        \n",
    "        if (self.isValid(nums, small, threshold)):\n",
    "            print(\"small valid: \" + str(small))\n",
    "            return math.ceil(small)\n",
    "        print(\"big valid: \" + str(big))\n",
    "        return math.ceil(big)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        length = len(nums)\n",
    "        right = max(nums)\n",
    "        while left<=right:\n",
    "            print(left, right)\n",
    "            mid = (left+right)//2\n",
    "            ans = sum([ceil(nums[i]/mid) for i in range(length)])\n",
    "            if ans > threshold:\n",
    "                # left左侧的都大于阈值\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                # ans <= threshold\n",
    "                # right自身以及右侧的值都小于等于阈值 \n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        m_ele=max(nums)\n",
    "        low=1\n",
    "        high=m_ele\n",
    "        while low<high:\n",
    "            mid=(low+high)//2\n",
    "            add=0\n",
    "            for n in nums:\n",
    "                add+=n//mid\n",
    "                if n%mid!=0:\n",
    "                    add+=1\n",
    "            if add <= threshold:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left, right = 1, max(nums)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum((i - 1) // mid + 1 for i in nums) <= threshold:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        l,r,ans = 1,max(nums)+1,1\n",
    "        while l <= r:\n",
    "            d = (r+l)//2\n",
    "            total = 0\n",
    "            for num in nums:\n",
    "                total += (num-1)//d + 1\n",
    "            if total <= threshold:\n",
    "                ans = d\n",
    "                r = d-1\n",
    "            else:\n",
    "                l = d+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def check(tn):\n",
    "            return sum(math.ceil(num / tn) for num in nums) <= threshold\n",
    "\n",
    "        def bis(left, right):\n",
    "            if right - left <= 1:\n",
    "                if check(left):\n",
    "                    return left\n",
    "                else:\n",
    "                    return right       \n",
    "            mid = int((left + right) / 2)\n",
    "            if check(mid):\n",
    "                return bis(left, mid)\n",
    "            else:\n",
    "                return bis(mid + 1, right)\n",
    "        return bis(1, max(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def div_sum(self, nums, div_num):\r\n",
    "        sum = 0\r\n",
    "        for num in nums:\r\n",
    "            sum += ceil(num / div_num)\r\n",
    "        print(\"div_num: \", div_num, \"sum: \", sum)\r\n",
    "        return sum\r\n",
    "\r\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\r\n",
    "        nums.sort()\r\n",
    "        left = 1    # left和right是除数\r\n",
    "        right = nums[-1]\r\n",
    "        while left <= right:\r\n",
    "            print(\"left: \", left, \"right: \", right)\r\n",
    "            mid = left + (right - left) // 2\r\n",
    "            if self.div_sum(nums, mid) > threshold:\r\n",
    "                left = mid + 1\r\n",
    "                continue\r\n",
    "            right = mid - 1\r\n",
    "\r\n",
    "        return left\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            s = 0\n",
    "            for x in nums:\n",
    "                s += (x + m - 1) // m\n",
    "                if s > threshold:\n",
    "                    return False\n",
    "            return s <= threshold\n",
    "        return bisect_left(range(1, max(nums)),True, key=lambda x: check(x)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left,right = 1,max(nums)\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            print(f\"mid={mid}\")\n",
    "            tmp = sum([ceil(x/mid) for x in nums])\n",
    "            print(f\"tmp={tmp}\")\n",
    "            if tmp>threshold:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Author: hqztrue\n",
    "# https://github.com/hqztrue/LeetCodeSolutions\n",
    "from ctypes import *\n",
    "import mmap\n",
    "\n",
    "#https://defuse.ca/online-x86-assembler.htm#disassembly2\n",
    "def translate(s):\n",
    "    res=b''\n",
    "    for l in s.split('\\n'):\n",
    "        if (not ':' in l) or (not '   ' in l): continue\n",
    "        l=l[l.find(':')+1:l.find('   ')].strip()\n",
    "        for b in l.split(' '):\n",
    "            res+=int(b,16).to_bytes(1,byteorder='little')\n",
    "    return res\n",
    "\n",
    "def compile_asm(s,ftype):\n",
    "    global buf\n",
    "    buf=mmap.mmap(-1,mmap.PAGESIZE,prot=mmap.PROT_READ|mmap.PROT_WRITE|mmap.PROT_EXEC)\n",
    "    fpointer=c_void_p.from_buffer(buf)\n",
    "    buf.write(translate(s))\n",
    "    return ftype(addressof(fpointer))\n",
    "\n",
    "'''\n",
    "int sum(int *a,int n,int d){\n",
    "    int s=0;\n",
    "    for (int i=0;i<n;++i)s+=a[i]/d;\n",
    "    return s;\n",
    "}\n",
    "'''\n",
    "asm_sum_div=compile_asm('''\n",
    "0:  89 d3                   mov    ebx,edx\n",
    "2:  b9 00 00 00 00          mov    ecx,0x0\n",
    "7:  48 8d 34 b7             lea    rsi,[rdi+rsi*4]\n",
    "000000000000000b <begin>:\n",
    "b:  8b 07                   mov    eax,DWORD PTR [rdi]\n",
    "d:  48 83 c7 04             add    rdi,0x4\n",
    "11: 99                      cdq\n",
    "12: f7 fb                   idiv   ebx\n",
    "14: 01 c1                   add    ecx,eax\n",
    "16: 48 39 f7                cmp    rdi,rsi\n",
    "19: 75 f0                   jne    b <begin>\n",
    "1b: 89 c8                   mov    eax,ecx\n",
    "1d: c3                      ret\n",
    "''',CFUNCTYPE(c_int,POINTER(c_int),c_int,c_int))\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        most = max(nums)\n",
    "        # l, r = ceil(sum(nums) / threshold), ceil(max(nums) / floor(threshold / n))\n",
    "        l = (s-1)//threshold+1\n",
    "        # if threshold > n:\n",
    "        #     r = min(most,(s-n-1)//(threshold-n)+1)\n",
    "        # else:\n",
    "        #     r = most\n",
    "        r = min(most,(s-n-1)//(threshold-n+1)+1)\n",
    "        #nums = [x-1 for x in nums]\n",
    "        a=(c_int*n)()\n",
    "        for i in range(n): a[i]=nums[i]-1\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            #cur = sum(n // mid for n in nums) + n\n",
    "            cur = asm_sum_div(a,n,mid) + n\n",
    "            if cur > threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        left = 1\n",
    "        length = len(nums)\n",
    "        right = max(nums)\n",
    "        while left<right:\n",
    "            print(left, right)\n",
    "            mid = (left+right)//2\n",
    "            ans = sum([ceil(nums[i]/mid) for i in range(length)])\n",
    "            if ans > threshold:\n",
    "                # left左侧的都大于阈值\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                # ans <= threshold\n",
    "                # right自身以及右侧的值都小于等于阈值 \n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        def help(d):\n",
    "            ans = 0\n",
    "            for n in nums:\n",
    "                ans = ans + math.ceil(n/d)\n",
    "            return ans\n",
    "        left = 1\n",
    "        right = max(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if help(mid) > threshold:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Author: hqztrue\n",
    "# https://github.com/hqztrue/LeetCodeSolutions\n",
    "from ctypes import *\n",
    "import mmap\n",
    "\n",
    "#https://defuse.ca/online-x86-assembler.htm#disassembly2\n",
    "def translate(s):\n",
    "    res=b''\n",
    "    for l in s.split('\\n'):\n",
    "        if (not ':' in l) or (not '   ' in l): continue\n",
    "        l=l[l.find(':')+1:l.find('   ')].strip()\n",
    "        for b in l.split(' '):\n",
    "            res+=int(b,16).to_bytes(1,byteorder='little')\n",
    "    return res\n",
    "\n",
    "def compile_asm(s,ftype):\n",
    "    global buf\n",
    "    buf=mmap.mmap(-1,mmap.PAGESIZE,prot=mmap.PROT_READ|mmap.PROT_WRITE|mmap.PROT_EXEC)\n",
    "    fpointer=c_void_p.from_buffer(buf)\n",
    "    buf.write(translate(s))\n",
    "    return ftype(addressof(fpointer))\n",
    "\n",
    "'''\n",
    "int sum(int *a,int n,int d){\n",
    "    int s=0;\n",
    "    for (int i=0;i<n;++i)s+=a[i]/d;\n",
    "    return s;\n",
    "}\n",
    "'''\n",
    "asm_sum_div=compile_asm('''\n",
    "0:  89 d3                   mov    ebx,edx\n",
    "2:  b9 00 00 00 00          mov    ecx,0x0\n",
    "7:  48 8d 34 b7             lea    rsi,[rdi+rsi*4]\n",
    "000000000000000b <begin>:\n",
    "b:  8b 07                   mov    eax,DWORD PTR [rdi]\n",
    "d:  48 83 c7 04             add    rdi,0x4\n",
    "11: 99                      cdq\n",
    "12: f7 fb                   idiv   ebx\n",
    "14: 01 c1                   add    ecx,eax\n",
    "16: 48 39 f7                cmp    rdi,rsi\n",
    "19: 75 f0                   jne    b <begin>\n",
    "1b: 89 c8                   mov    eax,ecx\n",
    "1d: c3                      ret\n",
    "''',CFUNCTYPE(c_int,POINTER(c_int),c_int,c_int))\n",
    "\n",
    "class Solution:\n",
    "    def smallestDivisor(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        most = max(nums)\n",
    "        l, r = ceil(sum(nums) / threshold), ceil(max(nums) / floor(threshold / n))\n",
    "        # l = (s-1)//threshold+1\n",
    "        # if threshold > n:\n",
    "        #     r = min(most,(s-n-1)//(threshold-n)+1)\n",
    "        # else:\n",
    "        #     r = most\n",
    "        #nums = [x-1 for x in nums]\n",
    "        a=(c_int*n)()\n",
    "        for i in range(n): a[i]=nums[i]-1\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            #cur = sum(n // mid for n in nums) + n\n",
    "            cur = asm_sum_div(a,n,mid) + n\n",
    "            if cur > threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
